# -*- coding: utf-8 -*-
# @Time  : 2021/7/21 下午10:51
# @Author : huangyuan
# @Project : algorithm
# @FileName: SortUtils.py
# @Description: 排序工具类

# 排序工具
import math
import random
from copy import copy

from common.utils.DateUtils import calculate_fun_runtime

# python中限制最大迭代深度为1000 下面语句是修改迭代最呆迭代深度
# sys.setrecursionlimit(100000)

# 归并排序,快速排序 当数组长度小于等于7是切换为插入排序
COUNT_OFFSET = 7


# 选择排序
@calculate_fun_runtime("选择排序")
def select_sort(array):
    if array_is_need_sort(array):
        array_len = len(array)
        for i in range(0, array_len - 1):
            # 找到的最小值放入数组最前面
            for j in range(i + 1, array_len):
                if array[i] > array[j]:
                    array[i], array[j] = array[j], array[i]


# 冒泡排序
@calculate_fun_runtime("冒泡排序")
def bubble_sort(array):
    if array_is_need_sort(array):
        array_len = len(array)
        for i in range(0, array_len):
            for j in range(0, array_len - i - 1):
                # 相邻的数进行大小比较, 将最大的数放入数组末尾
                if array[j] > array[j + 1]:
                    array[j], array[j + 1] = array[j + 1], array[j]


# 插入排序
# @calculate_fun_runtime("插入排序")
def insert_sort(array):
    if array_is_need_sort(array):
        array_len = len(array)
        for i in range(1, array_len):
            j = i
            #  保持前面数组有序，将后面的数组放入前面数组的合适位置
            while j - 1 >= 0 and array[j] < array[j - 1]:
                array[j], array[j - 1] = array[j - 1], array[j]
                j -= 1


# 部分插入排序
# low 数组起始下标
# high 数组结束下标
def insert_sort_part(array, low, high):
    array_len = len(array)
    if low < 0 or high >= array_len:
        return
    for i in range(low, high):
        # 找到的最小值放入数组最前面
        for j in range(i + 1, high + 1):
            if array[i] > array[j]:
                array[i], array[j] = array[j], array[i]


# 希尔排序
# 实行多次加大步长的插入排序，减少数组的逆序对，最后进行插入排序
@calculate_fun_runtime("希尔排序")
def shell_sort(array):
    if array_is_need_sort(array):
        array_len = len(array)
        h = 1
        # 设置步长
        while h < array_len // 3:
            h = 3 * h + 1
        while h >= 1:
            for i in range(h, array_len):
                j = i
                # 指定的步长的插入排序
                while j >= h and array[j] < array[j - h]:
                    # 满足条件的才加入循环中
                    array[j], array[j - h] = array[j - h], array[j]
                    j = j - h
            if array_is_sort(array):
                return
            # 交换长度递减
            h = h // 3


# 归并排序 - 先分后合
@calculate_fun_runtime("归并排序")
def merge_sort(array):
    if array_is_need_sort(array):
        array_len = len(array)
        # 当长度小于指定长度的时候使用插入排序，优化效率
        if array_len < COUNT_OFFSET:
            insert_sort(array)
            return
        merge(array, 0, array_len - 1)


# 合并函数
def merge(array, low, high):
    # 当归并排序的长度小于指定长度的时候采用插入排序提高效率
    if high - low <= 0:
        return
    # 如果数组有序直接返回
    if array_is_sort_part(array, low, high):
        return
    else:
        mid = (low + high) // 2
        # 如果数组本身就有序
        # 将数组一分为二进行递归
        merge(array, low, mid)
        merge(array, mid + 1, high)
        # 合并数组
        merge_array(array, low, mid, high)


# 归并排序 - 直接合并
@calculate_fun_runtime("归并排序-直接排序")
def merge_immediate(array):
    if array_is_need_sort(array):
        array_len = len(array)
        step = 1
        while step < array_len:
            low = 0
            while low < array_len - step:
                # 此处设置中间位置，当数组最后的长度不足时，在最后一次合并的时候将剩余的长度，和之前合并好的进行合并
                mid = low + step - 1
                merge_array(array, low, mid, min(low + step + step - 1, array_len - 1))
                low += step + step
            step += step


# 合并数组
def merge_array(array, low, mid, high):
    # 获取左右数组对长度
    left_array_len = mid - low + 1
    right_array_len = high - mid
    # 创建两个临时数组来对数组左右两边进行拷贝
    temp_left = copy(array[low:mid + 1])
    temp_right = copy(array[mid + 1:high + 1])
    # 初始化左指针
    i = 0
    # 初始化右指针
    j = 0
    index = low
    while index <= high:
        # 右边数都合并到数组，只用将左边的数往数组后面放
        if j >= right_array_len:
            array[index] = temp_left[i]
            i += 1
        # 左边数都合并到数组，只用将右边的数往数组后面放
        elif i >= left_array_len:
            array[index] = temp_right[j]
            j += 1
        # 小数优先放到数组前面
        elif temp_left[i] < temp_right[j]:
            array[index] = temp_left[i]
            i += 1
        else:
            array[index] = temp_right[j]
            j += 1
        index += 1


# 快速排序
# 快速排序在处理重复元素较多的数组排序时效率比较低下
# 所以改进的算法是进行3分区快速排序 具体思想是: 选准基准元素分为3个区域
@calculate_fun_runtime("快速排序")
def quick_sort(array):
    if array_is_need_sort(array):
        array_len = len(array)
        if array_len < COUNT_OFFSET:
            insert_sort(array)
            return
        quick(array, 0, array_len - 1)


# 快速排序
def quick(array, low, high):
    if low >= high:
        return
    if array_is_sort_part(array, low, high):
        return
    # 进行一趟快排
    position = partition(array, low, high)
    # 左边快排
    quick(array, low, position - 1)
    # 右边快排
    quick(array, position + 1, high)


# 一趟快排
def partition(array, low, high):
    base = array[low]
    left = low + 1
    right = high
    while True:
        # 从左边查找，找到比基准数大的数
        while left <= right and array[left] <= base:
            left += 1
        # 从右边查找，找到比基准数小的数
        while right >= left and array[right] >= base:
            right -= 1
        if left >= right:
            break
        # 交换数据
        array[left], array[right] = array[right], array[left]
    array[low], array[right] = array[right], array[low]
    return right


# 3分区快速排序
@calculate_fun_runtime("3分区快速排序")
def quick_3_way_sort(array):
    if array_is_need_sort(array):
        array_len = len(array)
        if array_len < COUNT_OFFSET:
            insert_sort(array)
            return
        quick_3_way(array, 0, array_len - 1)


# 3分区快排
def quick_3_way(array, low, high):
    if low >= high:
        return
    if array_is_sort_part(array, low, high):
        return
    left, right = three_partition(array, low, high)
    quick_3_way(array, low, left - 1)
    quick_3_way(array, right + 1, high)


# 3分区一趟快排
def three_partition(array, low, high):
    # 选定基数
    base = array[low]
    # 定义游标
    index = low + 1
    while index <= high:
        # 当前数小于基数，放到基数左边
        if array[index] < base:
            array[index], array[low] = array[low], array[index]
            index += 1
            low += 1
        # 当前数大于基数，放到右边
        elif array[index] > base:
            array[index], array[high] = array[high], array[index]
            high -= 1
        else:
            index += 1
    return low, high


# 堆排序
@calculate_fun_runtime("堆排序")
def heap_sort(array):
    if array_is_need_sort(array):
        array_len = len(array)
        N = array_len - 1
        # 将队列变为大数优先队列
        i = N // 2
        while i >= 1:
            sink(array, i, N)
            i -= 1
        # 将大数一个个移动到优先队列末尾
        while N > 1:
            array[1], array[N] = array[N], array[1]
            N -= 1
            sink(array, 1, N)
        # 将第一个元素，即下标为0的元素放入指定位置
        for j in range(0, array_len - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]


# 小节点下沉-以大数优先的队列思想
def sink(array, index, array_len):
    while index * 2 <= array_len:
        j = index * 2
        # 取较大的数
        if j < array_len and array[j + 1] > array[j]:
            j = j + 1
        # 如果本来就小于较小的数，就停止下沉
        if array[index] > array[j]:
            break
        array[index], array[j] = array[j], array[index]
        index = j


# 计数排序
# 数组要求是整数数组，并且值比较集中
@calculate_fun_runtime("计数排序")
def counting_sort(array):
    if array_is_need_sort(array):
        # 获取数组最值
        array_max = max(array)
        array_min = min(array)
        # 计算新数组长度
        count_array_len = array_max - array_min + 1
        count_array = [0 for i in range(0, count_array_len)]
        for value in array:
            # 计算当前值到数组最小值的距离，该距离最为在新数组中的下标
            count_array[value - array_min] += 1
        # 将新数组值连接起来，连接方式索引+array_min-> 对应索引的数值
        k = 0
        for i in range(0, count_array_len):
            for j in range(0, count_array[i]):
                array[k] = i + array_min
                k += 1


# 桶排序
# 计数排序的改进
@calculate_fun_runtime("桶排序")
def bucket_sort(array):
    if array_is_need_sort(array):
        array_len = len(array)
        # 获取数组最值
        array_max = max(array)
        array_min = min(array)
        # 确定区间长度 每个区间是均等的
        interval_range = (array_max - array_min) / (array_len - 1)
        # 桶数组
        buckets = []
        for i in range(0, array_len):
            # 为每个桶分配一个数组
            buckets.append([])
        # 将原数组元素放到对应的桶中
        for value in array:
            # 计算当前数处于那个桶中
            bucket_num = int(((value - array_min) / interval_range))
            # 将数值放入对应的桶中
            buckets[bucket_num].append(value)
        # 将数组都通过快速排序
        for bucket in buckets:
            quick_sort(bucket)
        # 将桶中排序好的数据依次放入原来的数组中
        k = 0
        for bucket in buckets:
            for value in bucket:
                array[k] = value
                k += 1


# 基数排序
# 适用范围 非负整数排序 且数值分布比较集中
@calculate_fun_runtime("基数排序")
def base_sort(array):
    if array_is_need_sort(array):
        array_len = len(array)
        # 获取数组最大值，确定取位轮数
        array_max = max(array)
        # 取位轮数
        fetch_bit_num = len(str(array_max))
        # 数据进桶 i标识根据第i位值来判断数据进入哪个基数桶
        i = 0
        while i < fetch_bit_num:
            # 创建0-9基数桶
            base_buckets = [[], [], [], [], [], [], [], [], [], []]
            for j in range(0, array_len):
                # 取每个数的第i位
                mod = int(array[j] / 10 ** i % 10)
                base_buckets[mod].append(array[j])
            # 将桶连接起来
            array.clear()
            for bucket in base_buckets:
                for value in bucket:
                    array.append(value)
            i += 1


# 判断数组是否有序
def array_is_sort(array):
    return array_is_sort_part(array, 0, len(array) - 1)


# 判断数组指定部分是否有序
def array_is_sort_part(array, low, high):
    for i in range(low, high):
        if array[i] > array[i + 1]:
            return False
    return True


# 判断数组是否需要排序
def array_is_need_sort(array):
    if array is None:
        return False
    array_len = len(array)
    if array_len < 2 or array_is_sort(array):
        return False
    return True


# 排序测试方法
def test_sort(sort_fun):
    array = create_random_array(1000000)
    # print(f"排序前数组: {array}")
    sort_fun(array)
    # print(f"排序后数组: {array}")
    # print("\n")


# 排序测试方法 浮点数
def test_sort_float(sort_fun):
    array = create_random_array_float(10)
    print(f"排序前数组: {array}")
    sort_fun(array)
    print(f"排序后数组: {array}")


# 测试三分区快排
def test_3_way_sort(sort_fun):
    array = create_random_duplicate_array(1000000)
    # print(f"排序前数组: {array}")
    sort_fun(array)
    # print(f"排序后数组: {array}")


# 生成规模为N的随机数组
@calculate_fun_runtime("生成数组")
def create_random_array(N):
    array = []
    for i in range(0, N):
        array.append(random.randint(0, N))
    return array


# 生成规模为N的随机浮点数
@calculate_fun_runtime("生成浮点数")
def create_random_array_float(N):
    array = []
    for i in range(0, N):
        array.append(random.random())
    return array


# 生成重复元素多的数组
@calculate_fun_runtime("生成元素重复数组")
def create_random_duplicate_array(N):
    array = []
    for i in range(0, N):
        array.append(random.randint(0, 50))
    return array


if __name__ == "__main__":
    # test_sort(select_sort)
    # test_sort(bubble_sort)
    # test_sort(insert_sort)
    # test_sort(shell_sort)
    # test_sort(merge_sort)
    # test_sort(merge_immediate)
    # test_sort(quick_sort)
    # test_3_way_sort(quick_sort)
    # test_3_way_sort(merge_sort)
    # test_3_way_sort(quick_3_way_sort)
    # test_sort(heap_sort)
    # test_sort(counting_sort)
    # test_sort_float(bucket_sort)
    test_3_way_sort(base_sort)
    test_sort(base_sort)
